#include <iostream>
#include <algorithm>
using namespace std;

const int N = 4;

int arr[N];

void InitSequence()
{
	for (int i = 0; i < N; ++i)
		arr[i] = i;
}

void PrintSequence()
{
	for (int i = 0; i < N; ++i)
		cout << arr[i];
	cout << endl;
}

// F(n) = n * F(n - 1) + 2 * n
// O(C * n!)
// Not in order
void PermutationA(int k)
{
	if (k >= N - 1)
	{
		PrintSequence();
		return;
	}

	for (int i = k; i < N; ++i)
	{
		swap(arr[k], arr[i]);
		PermutationA(k + 1);
		swap(arr[k], arr[i]);
	}
}

// F(n) = n * F(n - 1) + 2 * n
// O(C * n!)
// In order
void PermutationB(int k)
{
	if (k >= N - 1)
	{
		PrintSequence();
		return;
	}

	for (int i = k; i < N; ++i)
	{
		swap(arr[k], arr[i]);
		PermutationB(k + 1);
	}

	for (int i = N - 1; i >= k; --i)
		swap(arr[k], arr[i]);
}


bool used[N];
// O(n ^ n)
// in order
void PermutationC(int k)
{
	if (k == N)
	{
		PrintSequence();
		return;
	}

	for (int i = 0; i < N; ++i)
		if (!used[i])
		{
			used[i] = true;
			arr[k] = i;
			PermutationC(k + 1);
			used[i] = false;
		}
}

bool My_Next_Permutation()
{
	int i = N - 2;
	while (i >= 0 && arr[i] >= arr[i + 1])
		--i;
	if (i == -1) 
		return false;

	int j = N - 1;
	while (arr[j] <= arr[i])
		--j;
	swap(arr[i], arr[j]);

	for (int m = i + 1, n = N - 1; m < n; ++m, --n)
		swap(arr[m], arr[n]);

	return true;
}

// O(n * n!)
// in order
void PermutationD()
{
	do
	{
		PrintSequence();
	}
	while (My_Next_Permutation());
}

int main()
{
	InitSequence();
	PermutationA(0);
	cout << endl;

	InitSequence();
	PermutationB(0);
	cout << endl;

	InitSequence();
	memset(used, 0, sizeof(used));
	PermutationC(0);
	cout << endl;

	InitSequence();
	PermutationD();

    system("pause");
    return 0;
}
